home *** CD-ROM | disk | FTP | other *** search
/ System Booster / System Booster.iso / Texteditors / Origami / Sources / src / lib / bregex.c next >
Encoding:
C/C++ Source or Header  |  1996-09-27  |  56.1 KB  |  1,879 lines
  1. /************************************************************************
  2.  *    bregex -- The `Better/BuGless/Berg' Regular Expression library    *
  3.  *                                    *
  4.  *    Copyright (c) 1991-1993, by S.R. van den Berg, The Netherlands    *
  5.  *                                    *
  6.  *    See bregex.h for more info.                    *
  7.  *                                    *
  8.  *    You are not required to understand the sources in order to    *
  9.  *    use them (I suspect not many people could use them in that    *
  10.  *    case).    You can, however, admire them as a work of art :-).    *
  11.  ************************************************************************/
  12. #ifdef RCS
  13. static const char rcsid[]=
  14.  "$Id: bregex.c,v 1.5 1993/10/01 16:48:26 berg Exp $";
  15. #endif
  16. #include <sys/types.h>            /* size_t */
  17. #include <stddef.h>            /* offsetof() */
  18. #ifndef RE_nCHAR_CLASS
  19. #include <string.h>            /* strncmp() */
  20. #ifdef RE_nCTYPE
  21. #undef RE_nCTYPE
  22. #endif
  23. #else
  24. #ifndef RE_nERROR_REPORT
  25. #include <string.h>            /* strlen() */
  26. #else
  27. #ifdef RE_MEMCHR
  28. #include <string.h>            /* memchr() */
  29. #endif
  30. #endif
  31. #endif
  32. #ifndef RE_nCTYPE
  33. #include <ctype.h>
  34. #endif
  35. #define BREGEX_C_
  36. #include "bregex.h"
  37.  
  38. #ifndef offsetof
  39. #define offsetof(s,m) ((char*)&((s*)sizeof(s))->m-(char*)sizeof(s))
  40. #endif
  41. #define ioffsetof(struc,memb)    ((int)offsetof(struc,memb))
  42. #define maxindex(a)        (sizeof(a)/sizeof((a)[0])-1)
  43. #define STRLEN(a)        (sizeof(a)-1)
  44. #define mx(a,b)            ((a)>(b)?(a):(b))
  45. typedef unsigned char uschar;
  46. #define uchar            uschar
  47. #ifdef RE_nCTYPE
  48. #define islower(c)    ((unsigned)(c)-'a'<='z'-'a')
  49. #define isupper(c)    ((unsigned)(c)-'A'<='Z'-'A')
  50. #define isprint(c)    ((unsigned)(c)-' '<='~'-' ')      /* ASCII dependent */
  51. #define tolower(c)    ((c)-'A'+'a')
  52. #define toupper(c)    ((c)+'A'-'a')
  53. #define TO_LOWER(i)    (isupper(i)&&((i)+='a'-'A'))
  54. #else
  55. #ifndef const
  56. #define TO_LOWER(i)    ((i)=Tolower(i))
  57. #else
  58. #define TO_LOWER(i)    (isupper(i)&&((i)=Tolower(i)))
  59. #endif /* const */
  60. #endif /* RE_nCTYPE */
  61.  
  62. #define STARTSTACK    16          /* needed stacksize will solely depend */
  63. #define INCSTACK    16               /* on the length of the match */
  64.  
  65. #define BITS_P_CHAR    8     /* if you change this, everything goes with it */
  66. #define OPB        (1<<BITS_P_CHAR)          /* except the \x00 and */
  67.                                /* \000 encodings */
  68. #define C_BEG_GROUP    '('          /* if you prefer different symbols */
  69. #define C_OR        '|'                  /* here is your chance */
  70. #define C_END_GROUP    ')'
  71. #define C_0_OR_MORE    '*'
  72. #define C_0_OR_1    '?'
  73. #define C_1_OR_MORE    '+'
  74. #define C_DOT        '.'
  75. #define C_BOL        '^'
  76. #define C_EOL        '$'
  77. #define C_BEG_NUMBER    '{'
  78. #define C_SEP_NUMBER    ','
  79. #define C_END_NUMBER    '}'
  80. #define C_BEG_CLASS    '['
  81. #define C_BEG_CCLASS    '['
  82. #define C_DEL_CCLASS    ':'
  83. #define C_END_CCLASS    ']'
  84. #define C_NOT_CLASS    '^'
  85. #define C_RANGE        '-'
  86. #define C_END_CLASS    ']'
  87. #define C_ESCAPE    '\\'
  88.  
  89. #ifndef RE_nCHAR_CLASS          /* The order has to correspond with R_CC_* */
  90. static const char*const cclass[]={"alnum","alpha","blank","cntrl","digit",
  91.  "graph","lower","print","punct","space","upper","xdigit",0};
  92. #endif               /* the opcodes of the non-deterministic automaton */
  93.                      /* below OPB are the regular characters */
  94. #define OPC_CLASS    OPB              /* a bitmapped character class */
  95. #define OPC_DOT        (OPB+1)                    /* any character */
  96. #define OPC_BOL        (OPB+2)                /* beginning of line */
  97. #define OPC_EOL        (OPB+3)                      /* end of line */
  98. #define OPC_EPS        (OPB+4)            /* epsilon-transition (fork) */
  99. #define OPC_FIN        (OPB+5)                       /* finish */
  100. #define OPC_GOP        (OPB+6)                       /* group open */
  101. #define OPC_GCL        (OPB+7)                      /* group close */
  102.            /* Don't change any opcode here without checking skplen[] */
  103.  
  104. #define R_BEG_GROUP    (OPB|C_BEG_GROUP)             /* token values */
  105. #define R_OR        (OPB|C_OR)
  106. #define R_END_GROUP    (OPB|C_END_GROUP)
  107. #define R_0_OR_MORE    (OPB|C_0_OR_MORE)
  108. #define R_0_OR_1    (OPB|C_0_OR_1)
  109. #define R_1_OR_MORE    (OPB|C_1_OR_MORE)
  110. #define R_DOT        (OPB|C_DOT)
  111. #define R_BOL        (OPB|C_BOL)
  112. #define R_EOL        (OPB|C_EOL)
  113. #define R_BEG_NUMBER    (OPB|C_BEG_NUMBER)
  114. #define R_END_NUMBER    (OPB|C_END_NUMBER)
  115. #define R_BEG_CLASS    (OPB|C_BEG_CLASS)
  116. #define R_NOT_CLASS    (OPB|C_NOT_CLASS)
  117. #define R_RANGE        (OPB|C_RANGE)
  118. #define R_END_CLASS    (OPB|C_END_CLASS)
  119. #define R_CC_BASE    (2*OPB)
  120. #define R_CC_alnum    (R_CC_BASE)
  121. #define R_CC_alpha    (R_CC_BASE+1)
  122. #define R_CC_blank    (R_CC_BASE+2)
  123. #define R_CC_cntrl    (R_CC_BASE+3)
  124. #define R_CC_digit    (R_CC_BASE+4)
  125. #define R_CC_graph    (R_CC_BASE+5)
  126. #define R_CC_lower    (R_CC_BASE+6)
  127. #define R_CC_print    (R_CC_BASE+7)
  128. #define R_CC_punct    (R_CC_BASE+8)
  129. #define R_CC_space    (R_CC_BASE+9)
  130. #define R_CC_upper    (R_CC_BASE+10)
  131. #define R_CC_xdigit    (R_CC_BASE+11)
  132. #define R_CC_nothing    (R_CC_BASE+12)        /* has to be the last R_CC_* */
  133.  
  134. #define bit_type        unsigned
  135. #define bit_bits        (sizeof(bit_type)*BITS_P_CHAR)
  136. #define bit_index(which)    ((unsigned)(which)/bit_bits)
  137. #define bit_mask(which)        ((unsigned)1<<(unsigned)(which)%bit_bits)
  138. #define bit_toggle(name,which)    (name[bit_index(which)]^=bit_mask(which))
  139. #define bit_test(name,which)    (!!(name[bit_index(which)]&bit_mask(which)))
  140. #define bit_set(name,which,value)    \
  141.  (value?(name[bit_index(which)]|=bit_mask(which)):\
  142.  (name[bit_index(which)]&=~bit_mask(which)))
  143. #define bit_mindex(size)    (((size)+bit_bits-1)/bit_bits)
  144. #define bit_field(name,size)    bit_type name[bit_mindex(size)]
  145.  
  146. #ifdef RE_EMPTY_OR
  147. #ifdef RE_SURE_MINIMAL
  148. #undef RE_SURE_MINIMAL
  149. #endif
  150. #endif
  151. #ifndef RE_nERROR_DETECT
  152. #ifdef RE_SURE_MINIMAL
  153. #undef RE_SURE_MINIMAL
  154. #endif
  155. #endif
  156. #ifdef RE_HEX_CHAR
  157. #define HDIGIT
  158. #define BACKSL_CLASS
  159. #else
  160. #ifdef RE_OCT_CHAR
  161. #define HDIGIT
  162. #define BACKSL_CLASS
  163. #else
  164. #ifndef RE_nBRACES
  165. #define HDIGIT
  166. #endif
  167. #ifdef RE_SPEC_CHAR
  168. #define BACKSL_CLASS
  169. #endif
  170. #endif
  171. #endif
  172. #ifdef HDIGIT
  173. #define HEX2NUM
  174. #else
  175. #ifndef RE_nERROR_REPORT
  176. #define HEX2NUM
  177. #endif
  178. #endif
  179. #ifndef RE_nCASE_TABLE
  180. #define Tolower(c)    (igncase[c])
  181. #undef TO_LOWER
  182. #define TO_LOWER(i)    ((i)=Tolower(i))
  183. #else /* RE_nCASE_TABLE */
  184. #define Tolower(c)    tolower(c)
  185. #endif /* RE_nCASE_TABLE */
  186. #ifndef isblank
  187. #define isblank(c)    ((c)==' '||(c)=='\t')
  188. #endif
  189. #define SZ(x)        (sizeof(struct x))
  190. #define Ceps        (struct eps*)
  191. #define geno(to,add)    ((char*)(to)+(add))
  192. #define epso(to,add)    (Ceps geno(to,add))
  193. #define dif(high,low)    ((char*)(high)-(char*)(low))
  194. #define Jtable(p)    (((struct aligar*)(p))->table)
  195. #define SKIP_TOK    (1<<0)
  196. #define CLASS_TOK    (1<<1)
  197. #define ii        (aleps.topc)
  198. #define kk        (aleps.tnext)
  199. #define jj        (aleps.ua.jjua)
  200. #define jjp        (aleps.ua.tspawn)
  201. #define spawn        sp.awn
  202.  
  203. struct eps{unsigned opc;struct eps*stack;
  204.  union evu{struct eps*awn;void*oid;}sp;struct eps*next;};
  205. struct ALEPS{unsigned topc;struct eps*tnext;
  206.  union everyt{struct eps*tspawn;unsigned jjua;void*Irrelevoid;}ua;};
  207.  
  208. #ifdef RE_nCONCUR_COMPILE             /* some compilation temporaries */
  209. static struct eps*r;                    /* target object pointer */
  210. static uchar*p;                        /* regexp source pointer */
  211. static regex_t*gpreg;                    /* regex_t reference */
  212. static struct ALEPS aleps;  /* general purpose aligner and scratch variables */
  213. static uchar*cachea,*cachep;              /* cache at, cache resulting p */
  214. static size_t cacher;                  /* cache resulting delta r */
  215. static errorno;                         /* last error found */
  216. #ifdef RE_NSUBMAX
  217. static mnmatch;                      /* REG_NSUBMAX count cache */
  218. #endif
  219. #define VSO
  220. #define VS
  221. #define VSA
  222. #define VSD
  223. #else /* RE_nCONCUR_COMPILE */
  224. #define VSO    vs             /* to avoid static variables, use a */
  225. #define VS    VSO,               /* fake struct that is passed all the */
  226. #define VSS    struct Vs*const
  227. #define VSA    VSS VSO,
  228. #define VSD    VSS VSO;           /* way down the compilation functions */
  229. struct Vs{struct eps*r_;uchar*p_;regex_t*gpreg_;struct ALEPS aleps_;
  230.  uchar*cachea_,*cachep_;size_t cacher_;int errorno_;
  231. #ifdef RE_NSUBMAX
  232.  int mnmatch_;
  233. #endif
  234.  };
  235. #define r    (vs->r_)
  236. #define p    (vs->p_)
  237. #define gpreg    (vs->gpreg_)
  238. #define aleps    (vs->aleps_)
  239. #define cachea    (vs->cachea_)
  240. #define cachep    (vs->cachep_)
  241. #define cacher    (vs->cacher_)
  242. #define errorno (vs->errorno_)
  243. #define mnmatch (vs->mnmatch_)
  244. #endif /* RE_nCONCUR_COMPILE */
  245.  
  246. #ifndef RE_nCASE_TABLE
  247. static uchar bothcase[OPB],igncase[OPB];
  248. #endif
  249.  
  250. struct mchar{unsigned opcc_;struct eps*next1_;
  251.  struct evoi{struct eps*st_;const void*wh_;}p1_,p2_;};
  252. struct chclass{unsigned opcc;struct eps*next1;struct evoi pos1,pos2;
  253.  bit_field(c,OPB);};
  254. struct gop{unsigned opcgop;struct eps*gopnext;
  255.  union{unsigned nr;void*IRrelevoid;}gopp;};
  256. #define gcl    gop
  257. #ifdef RE_nJUMP_TABLE
  258. struct aligar{unsigned aopc;bit_field(table,OPB);};
  259. #else /* RE_nJUMP_TABLE */
  260. #ifdef RE_SMALL_JUMP_TABLE
  261. typedef uchar jt_type;
  262. #else
  263. typedef unsigned jt_type;
  264. #endif
  265. struct aligar{unsigned aopc;jt_type table[OPB];};
  266. #endif /* RE_nJUMP_TABLE */
  267.                       /* lenght array, used by skiplen() */
  268. static const char skplen[]={SZ(chclass),SZ(mchar),SZ(mchar),SZ(mchar),SZ(eps),
  269.  0
  270. #ifndef RE_pNOSUB
  271.  ,SZ(gop),SZ(gcl)
  272. #endif
  273.  };
  274.  
  275. #ifndef RE_nERROR_DETECT
  276. static void error(VS nr)VSD const unsigned nr;
  277. { if(!errorno||(uchar*)gpreg->re_es.re_stack>p)      /* no error yet?  earlier? */
  278.      errorno=nr,gpreg->re_es.re_stack=p;    /* ok, save it for posterity */
  279. }
  280. #else
  281. #define error(VS nr)
  282. #endif
  283.  
  284. #ifdef HEX2NUM
  285. static const char hex2num[]="0123456789abcdef";          /* to get rid of ASCII */
  286. #endif
  287. #ifdef HDIGIT
  288. static hdigit(d)                 /* returns 16 if non-xdigit */
  289. { register const char*chp;
  290.   TO_LOWER(d);
  291.   for(chp=hex2num-1;*++chp&&*chp!=d;);
  292.   return(int)(chp-hex2num);
  293. }
  294. #endif
  295.  
  296. static unsigned tok(VS type)VSD const int type;            /* get token */
  297. { register size_t i= *p;
  298. #ifndef RE_nEXTENDED
  299. #ifndef RE_pEXTENDED
  300.   register unsigned extended=gpreg->re_flags®_EXTENDED;     /* cache it */
  301. #endif
  302. #endif
  303.   if(type&CLASS_TOK)                      /* inside a class? */
  304.    { switch(i)
  305.       { case '\0':goto case_0;
  306.     case C_NOT_CLASS:case C_RANGE:case C_END_CLASS:goto o_case;
  307. #ifdef BACKSL_CLASS
  308.     case C_ESCAPE:goto e_case;
  309. #endif
  310. #ifndef RE_nCHAR_CLASS
  311.     case C_BEG_CCLASS:
  312.        if(p[1]==C_DEL_CCLASS)
  313.         { ;{ const uchar*cc=p+1;
  314.          do                 /* find the other delimiter */
  315.             if(!*++cc)
  316.              { error(VS REG_ECTYPE);break;    /* oops, end of string */
  317.              }
  318.          while(*cc!=C_DEL_CCLASS||cc[1]!=C_END_CCLASS);
  319.          i=cc-p-2;                 /* how long was it now? */
  320.            }
  321.           ;{ const char*const*ccp;           /* do we have that name here? */
  322.          for(ccp=cclass;strncmp(*ccp,(char*)p+2,i)||(*ccp)[i];)
  323.             if(!*++ccp)
  324.              { error(VS REG_ECTYPE);break;   /* oops, past last name */
  325.              }
  326.          if(p[i+=2]&&p[++i])          /* carefully sense the end */
  327.             i++;
  328.          if(type&SKIP_TOK)
  329.             p+=i;                 /* actually skip it now */
  330.          return R_CC_BASE+ccp-cclass;
  331.            }
  332.         }
  333. #endif
  334.       }
  335.    }
  336.   switch(i)
  337.    { case '\0':
  338. case_0: return R_END_GROUP;
  339.      case C_ESCAPE:
  340. e_case: switch(i=p[1])
  341.      { case '\0':i=C_ESCAPE;error(VS REG_EESCAPE);goto once;
  342. #ifdef RE_HEX_CHAR
  343.        case 'x':                             /* \x00 */
  344.           if(hdigit(i)<16)
  345.            { i=hdigit(i);
  346.          if(hdigit(p[3])<16)
  347.           { i=(i<<4)+hdigit(p[3]);
  348. #ifdef RE_OCT_CHAR
  349.             goto skip2;
  350.           }
  351.          else
  352.             goto skip1;
  353. #else
  354.             if(type&SKIP_TOK)
  355.                p+=2;
  356.           }
  357.          else if(type&SKIP_TOK)
  358.             p++;
  359. #endif
  360.            }
  361.           break;
  362. #endif
  363. #ifdef RE_OCT_CHAR
  364.        default:                             /* \000 */
  365.           if(hdigit(i)<8)
  366.            { i=hdigit(i);
  367.          if(hdigit(p[2])<8)
  368.           { i=(i<<3)+hdigit(p[2]);
  369.             if(hdigit(p[3])<8)
  370.              { i=(i<<3)+hdigit(p[3]);
  371. skip2:               if(type&SKIP_TOK)
  372.               p+=2;
  373.              }
  374.             else
  375. skip1:               if(type&SKIP_TOK)
  376.               p++;
  377.           }
  378.            }
  379.           break;
  380. #endif /* RE_OCT_CHAR */
  381. #ifdef RE_SPEC_CHAR
  382.        case 'a':i='\a';break;
  383.        case 'b':i='\b';break;
  384.        case 'f':i='\f';break;
  385.        case 'n':i='\n';break;
  386.        case 'r':i='\r';break;
  387.        case 't':i='\t';break;
  388.        case 'v':i='\v';break;
  389. #endif
  390. #ifndef RE_pEXTENDED
  391.        case C_0_OR_1:case C_1_OR_MORE:case C_BEG_GROUP:case C_OR:
  392.        case C_END_GROUP:
  393. #ifndef RE_nBRACES
  394.        case C_BEG_NUMBER:case C_END_NUMBER:
  395. #endif
  396. #ifndef RE_nEXTENDED
  397.           if(!extended)
  398. #endif
  399.          i|=OPB;
  400. #endif /* RE_pEXTENDED */
  401.      }
  402.     if(type&SKIP_TOK)
  403.        p++;
  404.     break;
  405. #ifndef RE_nEXTENDED
  406.      case C_0_OR_1:case C_1_OR_MORE:case C_BEG_GROUP:case C_OR:
  407.      case C_END_GROUP:
  408. #ifndef RE_nBRACES
  409.      case C_BEG_NUMBER:case C_END_NUMBER:
  410. #endif
  411. #ifndef RE_pEXTENDED
  412.     if(!extended)
  413.        break;
  414. #endif
  415. #endif /* RE_nEXTENDED */
  416.      case C_0_OR_MORE:case C_DOT:case C_BOL:case C_EOL:case C_BEG_CLASS:
  417.     if(!(type&CLASS_TOK))
  418. o_case:       i|=OPB;
  419.    }
  420. once:
  421.   if(type&SKIP_TOK)                     /* skip it as well? */
  422.      p++;
  423.   return i;                           /* return token found */
  424. }
  425.  
  426. static unsigned token(VSO)VSD                     /* normal token */
  427. { return tok(VS 0);
  428. }
  429.  
  430. static unsigned skiptok(VSO)VSD                /* skip normal token */
  431. { return tok(VS SKIP_TOK);
  432. }
  433.  
  434. static unsigned classtok(VSO)VSD               /* token in class */
  435. { return tok(VS CLASS_TOK);
  436. }
  437.  
  438. static unsigned skipclass(VSO)VSD              /* skip token in class */
  439. { return tok(VS CLASS_TOK|SKIP_TOK);
  440. }
  441.                                /* epsilon transition */
  442. static void puteps(spot,to,aswell)struct eps*const spot;
  443.  const struct eps*const to,*const aswell;
  444. { spot->opc=OPC_EPS;spot->next=to!=spot?Ceps to:Ceps aswell;
  445.   spot->spawn=aswell!=spot?Ceps aswell:Ceps to;
  446. #ifndef RE_SURE_MINIMAL
  447.   spot->stack=0;     /* zero stack; cstack(), the optimiser, needs this! */
  448. #endif
  449. }
  450.  
  451. static void putneps(spot,to)struct eps*const spot;const struct eps*const to;
  452. { puteps(spot,to,spot+1);      /* epsilon transition, one branch to the next */
  453. }
  454.  
  455. #define Cc(p,memb)    (((struct chclass*)(p))->memb)
  456. #define Go(p,memb)    (((struct gop*)(p))->memb)
  457. #define Gc(p,memb)    (((struct gcl*)(p))->memb)
  458. #define rAc        Cc(r,c)
  459.  
  460. static void bseti(VS fld,i,j)VSD bit_field(fld,OPB);unsigned i;
  461.  const unsigned j;
  462. { bit_set(fld,i,j);               /* mark 'i' as being in the class */
  463.   if(gpreg->re_flags®_ICASE)              /* mark the other case too */
  464.    { if(islower(i))                        /* lowercase */
  465.     i=toupper(i);
  466.      else
  467.     TO_LOWER(i);                        /* uppercase */
  468.      bit_set(fld,i,j);
  469.    }
  470. }
  471.                        /* general purpose length routine */
  472. static struct eps*skiplen(ep)const struct eps*const ep;
  473. { return epso(ep,ep->opc<OPB?SZ(mchar):skplen[ep->opc-OPB]);
  474. }
  475.  
  476. static void initbitm(fld,reset)bit_type*fld;const unsigned reset;
  477. { register unsigned i=bit_mindex(OPB);
  478.   do fld[--i]=reset?0:~(bit_type)0;             /* preset the bit field */
  479.   while(i);
  480. }
  481.  
  482. static void initsimp(rp,e)struct eps*rp,*e;
  483. { Cc(rp,next1)=e;Cc(rp,pos1.st_)=Cc(rp,pos2.st_)=0;    /* init thiss & other */
  484. #ifndef RE_nJUMP_TABLE     /* stacks to 0 (regexec() & initjtable() need this) */
  485.   Cc(rp,pos2.wh_)=0;
  486. #endif
  487. }
  488.                /* we need one forward declaration to allow recursion */
  489. static por P((VSA const struct eps*const e));
  490.  
  491. #define IN_CLASS(CLASS,class)    \
  492.  case CLASS:\
  493.     if(class(cc))\
  494.        break;\
  495.     continue
  496.  
  497. static void psimp(VS e)VSD const struct eps*e;         /* put a simple element */
  498. { register union{unsigned uns;struct eps*epp;}u;     /* save stack space */
  499.   register union{unsigned i;void*pold;}v;        /* for the recursion */
  500.   switch(token(VSO))
  501.    { case R_BEG_GROUP:skiptok(VSO);          /* not so simple after all */
  502. #ifndef RE_pNOSUB                /* are we exceeding REG_NSUBMAX? */
  503.     if(!e||gpreg->re_flags®_NOSUB
  504. #ifdef RE_NSUBMAX
  505.      ||gpreg->re_flags®_NSUBMAX&&gpreg->re_nsub>=mnmatch
  506. #endif
  507.                                    )
  508.      { if(por(VS e))
  509.           error(VS REG_EPAREN);
  510. #ifndef RE_nBRACES      /* we need these fillers, identical subexpressions */
  511.        if(e)       /* must have the same lengths (pnorm() depends on it) */
  512.           r->opc=OPC_GOP;          /* also, bogus opcodes are not allowed */
  513.        r=epso(r,SZ(gop));          /* e.g. findandrep() depends on it */
  514.        if(!e)
  515.           goto no_e;
  516. #else
  517.        r=epso(r,SZ(gop)+SZ(gcl));return;
  518. #endif
  519.      }
  520.     else                  /* insert the numbered paren pairs */
  521.      { (u.epp=r)->opc=OPC_GOP;r=epso(u.epp,SZ(gop));
  522.        u.epp->stack=epso(u.epp,SZ(gop));   /* remember the spot of the ( */
  523.        Go(u.epp,gopp.nr)= ++gpreg->re_nsub;v.pold=p;por(VS Ceps 0);
  524.        p=v.pold;r->stack=Ceps e;Gc(e=r,gopp.nr)=Go(u.epp,gopp.nr);
  525.        r=epso(u.epp,SZ(gop));        /* match up the ) with the ( */
  526.        if(por(VS e))                  /* insert the meat */
  527.           error(VS REG_EPAREN);
  528.      }
  529.     r->opc=OPC_GCL;
  530. no_e:    r=epso(r,SZ(gcl));return;
  531. #else /* RE_pNOSUB */
  532.     if(por(VS e))
  533.        error(VS REG_EPAREN);
  534.     return;
  535. #endif /* RE_pNOSUB */
  536.      case R_BEG_CLASS:                       /* a simple class */
  537.     skiptok(VSO);u.uns=C_NOT_CLASS!=*p;          /* `not' modifier? */
  538.     if(e)
  539.        r->opc=OPC_CLASS,initsimp(r,Ceps e),initbitm(rAc,u.uns);
  540.     if(!u.uns)                  /* skip the `not' modifier */
  541.      { p++;
  542. #ifndef RE_nNEWLINE
  543. #ifdef RE_pNEWLINE
  544.        if(e)
  545. #else
  546.        if(e&&gpreg->re_flags®_NEWLINE)         /* newlines are special */
  547. #endif
  548.           bit_toggle(rAc,'\n');
  549. #endif
  550.      }
  551.     if(*p==C_END_CLASS)      /* right at the start, cannot mean the end */
  552.      { p++;
  553.        if(e)
  554.           v.i=C_END_CLASS,bit_toggle(rAc,C_END_CLASS);
  555.      }
  556.     else if(*p==C_RANGE)                /* take it literally */
  557.      { p++;
  558.        if(e)
  559.           v.i=C_RANGE,bit_toggle(rAc,C_RANGE);
  560.      }
  561.     for(;;skipclass(VSO))               /* skip through the class */
  562.      { switch(classtok(VSO))
  563.         { case R_END_GROUP:error(VS REG_EBRACK);
  564.           case R_END_CLASS:skipclass(VSO);r=epso(r,SZ(chclass));
  565.          return;
  566. #ifndef RE_nCHAR_CLASS
  567.           case R_CC_alnum:case R_CC_alpha:case R_CC_blank:case R_CC_cntrl:
  568.           case R_CC_digit:case R_CC_graph:case R_CC_lower:case R_CC_print:
  569.           case R_CC_punct:case R_CC_space:case R_CC_upper:case R_CC_xdigit:
  570.          if(e)
  571.           { unsigned cc;
  572.             v.i=classtok(VSO);cc=OPB-1;
  573.             do
  574.              { switch(v.i)
  575.             { IN_CLASS(R_CC_alnum,isalnum);
  576.               IN_CLASS(R_CC_alpha,isalpha);
  577.               IN_CLASS(R_CC_blank,isblank);
  578.               IN_CLASS(R_CC_cntrl,iscntrl);
  579.               IN_CLASS(R_CC_digit,isdigit);
  580.               IN_CLASS(R_CC_graph,isgraph);
  581.               IN_CLASS(R_CC_lower,islower);
  582.               IN_CLASS(R_CC_print,isprint);
  583.               IN_CLASS(R_CC_punct,ispunct);
  584.               IN_CLASS(R_CC_space,isspace);
  585.               IN_CLASS(R_CC_upper,isupper);
  586.               default:
  587.                  if(!isxdigit(cc))
  588.                 continue;
  589.             }              /* it's in the character class */
  590.                bseti(VS rAc,cc,u.uns);               /* so mark it */
  591.              }
  592.             while(cc--);      /* walk through the whole alphabet */
  593.           }
  594.           case R_CC_nothing:v.i=OPB;continue;    /* erroneous char class */
  595. #endif
  596.           case R_RANGE:p++;
  597.          switch(classtok(VSO))
  598.           { default:
  599.                if(e)                /* mark all in range */
  600.             { while(++v.i<(classtok(VSO)&(OPB-1)))      /* careful */
  601.                  bseti(VS rAc,v.i&(OPB-1),u.uns);    /* with mask */
  602. #ifndef RE_nERROR_DETECT                /* to stay within bounds */
  603.               if(v.i!=(classtok(VSO)&(OPB-1))
  604. #ifndef RE_nCHAR_CLASS
  605.                ||classtok(VSO)>=R_CC_BASE
  606. #endif
  607.                               )
  608.                  error(VS REG_ERANGE);
  609. #endif
  610.             }
  611.                break;
  612.             case R_END_CLASS:p--;            /* literally */
  613.             case R_END_GROUP:;
  614.           }
  615.         }
  616.        if(e)                   /* regular character, mark it */
  617.           bseti(VS rAc,v.i=classtok(VSO),u.uns);
  618.      }
  619.      case R_END_GROUP:return;
  620.      case R_DOT:             /* matches everything but a newline */
  621.     if(e)                        /* if REG_NEWLINE is set */
  622.      { u.uns=OPC_DOT;goto fine;
  623.      }
  624.     goto fine2;
  625.      case R_BOL:                    /* beginning of line */
  626.     if(e)
  627.      { u.uns=OPC_BOL;goto finep;
  628.      }
  629.     goto fine2;
  630.      case R_EOL:                          /* end of line */
  631.     if(e)
  632.      { u.uns=OPC_EOL;
  633. finep:
  634. #ifndef RE_DUMB_ANCHOR
  635.        Cc(r,pos1.wh_)=p;
  636. #endif
  637.        goto fine;
  638.      }
  639.     goto fine2;
  640.    }
  641.   if(e)                              /* a regular character */
  642. #ifndef RE_nERROR_DETECT
  643.    { if((u.uns=token(VSO))>=OPB)
  644.     error(VS REG_BADRPT),u.uns&=OPB-1;
  645. #else
  646.    { u.uns=token(VSO)&OPB-1;
  647. #endif
  648. fine:
  649.      r->opc=u.uns<OPB&&gpreg->re_flags®_ICASE&&isupper(u.uns)?
  650.       Tolower(u.uns):u.uns;
  651.      initsimp(r,Ceps e);
  652.    }
  653. fine2:
  654.   skiptok(VSO);r=epso(r,SZ(mchar));    /* advance source and target pointers */
  655. }
  656.  
  657. #define PROGID    const char progid[]=\
  658.  "Bregex library, copyright (c) 1991-1993, S.R. van den Berg, The Netherlands"
  659.  
  660. #ifndef RE_nBRACES
  661. static dec(VSO)VSD               /* return a decimal for {.. , ..} */
  662. { unsigned i=0;
  663.   while(hdigit(*p)<10)
  664.      i=i*10+hdigit(*p++);
  665.   return i;
  666. }
  667.  
  668. static skipend(VSO)VSD             /* check if we are close before the end */
  669. { switch(token(VSO))                    /* anything special? */
  670.    { case R_OR:case R_END_GROUP:            /* the end in person */
  671.     goto ret1;
  672.      case R_BEG_NUMBER:                    /* something complicated */
  673.     for(;;)                   /* start searching for its complement */
  674.        switch(skiptok(VSO))
  675.         { case R_END_GROUP:goto ret1;           /* how unexpected */
  676.           case R_END_NUMBER:goto skippend;          /* how predictable */
  677.         }
  678.      case R_0_OR_MORE:case R_1_OR_MORE:case R_0_OR_1:case R_END_NUMBER:
  679.     skiptok(VSO);                           /* how casual */
  680. skippend:
  681.     switch(token(VSO))                  /* look one step ahead */
  682.      { case R_OR:case R_END_GROUP:         /* so it ends here afterall */
  683. ret1:          return 1;
  684.      }
  685.    }
  686.   return 0;                   /* then again, it doesn't have to */
  687. }
  688.  
  689. #define EOS(x)    (kk?kk:(x))         /* real end, or continue with the next? */
  690.  
  691. static void pnorm(VS e)VSD const struct eps*const e;      /* put normal text */
  692. { void*pold;int i;union{struct eps*old;unsigned len;}q;
  693.   for(;;)                           /* get the length */
  694.    { i=0;pold=p;q.old=r;psimp(VS Ceps 0);q.len=dif(r,q.old);     /* store it */
  695.      if(e)                  /* we really want to generate code */
  696.     r=epso(r,-(int)q.len);               /* backup before we start */
  697.      switch(token(VSO))                /* anything special trailing it? */
  698.       {
  699. #ifndef RE_pNOSUB
  700.     unsigned pin;
  701. #endif
  702.     case R_0_OR_MORE:ii=0;goto procj0;     /* ii indicates the minimum */
  703.     case R_1_OR_MORE:ii=1;                /* no. of occurances */
  704. procj0:       jj=0;goto proc;             /* jj indicates the maximum */
  705.     case R_0_OR_1:ii=0;goto procj1;            /* no. of occurances */
  706.     default:ii=1;
  707. procj1:       jj=1;goto proc;
  708.     case R_BEG_NUMBER:
  709. #ifndef RE_pNOSUB
  710.        for(;;gpreg->re_nsub=pin)        /* restore it from our excursion */
  711. #else
  712.        for(;;)
  713. #endif
  714.         { skiptok(VSO);ii=dec(VSO);jj=C_SEP_NUMBER==*p?(p++,dec(VSO)):ii;
  715. #ifndef RE_nERROR_DETECT
  716.           if(token(VSO)!=R_END_NUMBER)
  717.          error(VS REG_EBRACE);
  718. #endif
  719. proc:          if(jj)
  720.            {
  721. #ifndef RE_SURE_MINIMAL
  722.          if(ii>jj)
  723.           { error(VS REG_BADBR);jj=ii;
  724.           }
  725. #endif
  726.          if(!e)                 /* only calculating the length? */
  727.           { r=epso(r+jj-ii,q.len*(jj-1));goto eit; /* use a shortcut */
  728.           }
  729.            }
  730.           else if(!e)
  731.            { r++;
  732.          if(ii)
  733.             r=epso(r,q.len*(ii-1));           /* different shortcut */
  734.          goto eit;
  735.            }
  736.           kk=skipend(VSO)?Ceps e:Ceps 0;p=pold;
  737.           if(++i<ii)          /* while we're still below the minimum */
  738. #ifdef RE_pNOSUB
  739.          psimp(VS epso(r,q.len));
  740.           else if(i==ii)
  741. #else                    /* keep the paren groups out of our hair */
  742.            { pin=gpreg->re_flags;gpreg->re_flags|=REG_NOSUB;
  743.          psimp(VS epso(r,q.len));gpreg->re_flags=pin;
  744.            }             /* keep the paren group number the same */
  745.           else if(pin=gpreg->re_nsub,i==ii)            /* while copying */
  746. #endif
  747.            { if(i==jj)                    /* last copy */
  748.           { psimp(VS EOS(epso(r,q.len)));goto eit;
  749.           }
  750.          if(!jj)                   /* maximum is infinit */
  751.           { puteps(epso(r,q.len),r,EOS(epso(r,q.len)+1));    /* loop */
  752.             psimp(VS epso(r,q.len));r++;goto eit;
  753.           }
  754.          psimp(VS epso(r,q.len));                /* plain */
  755.            }
  756.           else if(!jj)                   /* maximum is infinit */
  757.            { putneps(r,EOS(epso(r+1,q.len)));psimp(VS r++);goto eit;
  758.            }
  759.           else if(i==jj)                  /* maximum reached */
  760.            { putneps(r,EOS(epso(r+1,q.len)));r++;
  761.          psimp(VS EOS(epso(r,q.len)));
  762. eit:         if(skipend(VSO))                /* real end? */
  763.             return;
  764.          break;
  765.            }
  766.           else                            /* plain */
  767.            { putneps(r,EOS(epso(r,(q.len+SZ(eps))*(1+jj-i))));
  768.          psimp(VS epso(++r,q.len));
  769.            }
  770.         }
  771.       }
  772.    }
  773. }
  774. #else /* RE_nBRACES */
  775. #define EOS(x)    (jjp?jjp:(x))
  776.  
  777. static void pnorm(VS e)VSD const struct eps*const e;      /* put normal text */
  778. { void*pold;struct eps*rold;
  779.   for(;;)                            /* skip it first */
  780.    { pold=p;rold=r;psimp(VS Ceps 0);
  781.      if(!e)                       /* if we're just counting */
  782.     pold=p;                           /* remember this spot */
  783.      ii=token(VSO);skiptok(VSO);
  784.      if(e)
  785.       { p=pold;pold=r;
  786.     jjp=token(VSO)==R_OR||token(VSO)==R_END_GROUP?Ceps e:Ceps 0;
  787.       }
  788.      switch(ii)               /* check for any of the postfix operators */
  789.       { case R_0_OR_MORE:r++;
  790.        if(e)              /* first an epsilon, then the rest */
  791.           putneps(rold,EOS(r)),r=rold+1,psimp(VS rold);
  792.        goto incagoon;
  793.     case R_1_OR_MORE:                   /* first the rest */
  794.        if(e)                      /* and then an epsilon */
  795.           puteps(r,rold,EOS(r+1)),r=rold,psimp(VS Ceps pold);
  796.        r++;goto incagoon;
  797.     case R_0_OR_1:r++;
  798.        if(e)              /* first an epsilon, then the rest */
  799.           putneps(rold,r=EOS(r)),pold=r,r=rold+1,psimp(VS Ceps pold);
  800. incagoon:  switch(skiptok(VSO))        /* at the end of this group already? */
  801.         { case R_OR:case R_END_GROUP:return;
  802.         }
  803.        continue;                 /* regular end of the group */
  804.     case R_OR:case R_END_GROUP:case '\0':
  805.        if(e)
  806.           r=rold,psimp(VS e);
  807.        return;
  808.       }
  809.      if(e)            /* no fancy postfix operators, plain vanilla */
  810.     r=rold,psimp(VS Ceps pold);
  811.      else
  812.     p=pold;
  813.    }
  814. }
  815. #endif /* RE_nBRACES */
  816.  
  817. static PROGID;
  818.  
  819. static por(VS e)VSD const struct eps*const e;          /* put an or-group */
  820. { uchar*pvold;struct eps*rvold;
  821.   if(!e)                       /* if we're only counting */
  822.    { rvold=r;
  823.      if(cachea==(pvold=p))                  /* check the cache */
  824.       { p=cachep;r=epso(rvold,cacher);goto ret0;         /* yep, hit */
  825.       }          /* if the cache is taken out, compile time rises exponentially */
  826.    }                     /* with the number of nested parens */
  827.   for(;;)
  828.    { uchar*pold;struct eps*rold;
  829.      for(pold=p,rold=r;;)
  830.       { switch(token(VSO))
  831.      { default:pnorm(VS Ceps 0);r=rold;continue;  /* still in this group */
  832.        case R_END_GROUP:               /* found the end of the group */
  833. #ifdef RE_EMPTY_OR
  834.           if(p==pold)                 /* empty `or' group */
  835.            { if(e)
  836.             puteps(r,e,e);        /* misused epsilon as branch */
  837.          r++;
  838.            }
  839.           else
  840. #endif
  841.          p=pold,pnorm(VS e);            /* normal last group */
  842.           if(!e)            /* only counting?  refresh the cache */
  843.            { skiptok(VSO);cachea=pvold;cachep=p;cacher=dif(r,rvold);
  844.          goto ret0;
  845.            }
  846.           if(*p)
  847.            { skiptok(VSO);
  848. ret0:         return 0;
  849.            }
  850.           return 1;
  851.        case R_OR:r++;
  852. #ifdef RE_EMPTY_OR
  853.           if(p==pold)                 /* empty `or' group */
  854.            { if(e)
  855.             putneps(rold,e);              /* special epsilon */
  856.            }
  857.           else
  858. #endif
  859.            { p=pold;pnorm(VS e);          /* normal `or' group, first an */
  860.          if(e)                   /* epsilon, then the rest */
  861.             putneps(rold,r);
  862.            }
  863.           skiptok(VSO);
  864.      }
  865.     break;
  866.       }
  867.    }
  868. }
  869.  
  870. #ifndef RE_SURE_MINIMAL
  871. static void findandrep(VS old,newv)VSD register struct eps**const old;
  872.  struct eps*const newv;
  873. { register struct eps*i,*t= *old;
  874.   for(i=r;;i=skiplen(i))        /* change all pointers from *old to newv */
  875.    { switch(i->opc)
  876.       { case OPC_FIN:*old=t;return;               /* last one, finished */
  877.     case OPC_EPS:
  878.        if(i->next==t)
  879.           i->next=newv;
  880.        if(i->spawn==t)
  881.           i->spawn=newv;
  882.        continue;
  883.       }
  884.      if(i->stack==t)
  885.     i->stack=newv;
  886.    }
  887. }
  888.  
  889. #define drs(m)    (*(struct eps**)geno(*stack,ioffsetof(struct eps,m)^ofs))
  890. #define RETyes    1
  891. #define RETno    0
  892.  
  893. #ifndef RE_pNOSUB
  894. #undef RETyes
  895. #undef RETno
  896. #define RETyes    ((struct eps**)0)
  897. #define RETno    nst
  898.  
  899. static struct eps**cstack(VS stack,ofs)VSD struct eps**const stack;
  900. { struct eps**nst;
  901.   for(nst= &drs(next);;)
  902.    { switch((*nst)->opc)
  903.       { case OPC_GOP:case OPC_GCL:nst= &(*nst)->stack;continue;
  904.       }
  905.      break;
  906.    }
  907. #else
  908. #define nst    (&drs(next))
  909. static cstack(VS stack,ofs)VSD struct eps**const stack;
  910. {
  911. #endif /* RE_pNOSUB */
  912.   if((*nst)->stack==Ceps p)
  913.    { findandrep(VS *(struct eps***)stack,drs(next));*stack=drs(spawn);
  914.      return RETyes;
  915.    }
  916.   return RETno;
  917. }
  918.     /* break up any closed epsilon circles, otherwise they can't be executed */
  919. static fillout(VS stack)VSD struct eps**const stack;
  920. {
  921. #ifndef RE_pNOSUB
  922.   struct eps**nst;
  923. #endif
  924.   if((*stack)->opc!=OPC_EPS||(*stack)->stack)
  925.      return 0;
  926.   (*stack)->stack=Ceps p;                /* mark this one as used */
  927. #ifndef RE_pNOSUB
  928. #define RECURS(nxt)    \
  929.   do\
  930.    { if(!(nst=cstack(VS (struct eps**)stack,\
  931.       ioffsetof(struct eps,nxt)^ioffsetof(struct eps,next))))\
  932.     return 1;\
  933.    }\
  934.   while(fillout(VS nst))
  935. #else /* RE_pNOSUB */
  936. #define RECURS(nxt)    \
  937.   do\
  938.      if(cstack(VS (struct eps**)stack,\
  939.       ioffsetof(struct eps,nxt)^ioffsetof(struct eps,next)))\
  940.     return 1;\
  941.   while(fillout(VS &(*stack)->nxt))
  942. #endif /* RE_pNOSUB */
  943.   RECURS(next);RECURS(spawn);return 0;                  /* recurse */
  944. }
  945. #endif /* RE_SURE_MINIMAL */
  946.  
  947. #define XOR1        \
  948.  (ioffsetof(struct chclass,pos1)^ioffsetof(struct chclass,pos2))
  949. #define PC(thiss,t)    (((struct evoi*)geno(thiss,t))->st_)
  950. #define PCp(thiss,t)    (((struct evoi*)geno(thiss,t))->wh_)
  951. #define PCs(s,thiss,t)    (*(struct eps**)((s)=(void*)&PC(thiss,t)))
  952. #define PCps(s,thiss,t) ((uchar*)*(const void**)\
  953.  geno(&PCs(s,thiss,t),ioffsetof(struct evoi,wh_)))
  954. #define Pci(thiss,t)    PCs(c,thiss,t)
  955. #define Pc()        (*(struct eps**)c)
  956. #define Pcp()        (*(const void**)(c+=ioffsetof(struct evoi,wh_)))
  957. #define PcP()        (*(const void**)c)
  958.  
  959. static void initjtable(VSO)VSD
  960. #ifndef RE_nJUMP_TABLE
  961. { typedef int goodness;
  962.   goodness bestval;jt_type*bt=Jtable(gpreg->re_finpoint);
  963.   unsigned depth,maxdepth,th1,ot1;
  964.   register struct eps*stack,*thiss,*other,*code,*s;jt_type jt[OPB];
  965.   ;{ register i=OPB-1;
  966.      while(jt[i]=0,i--);              /* pre-init our jump table */
  967.    }
  968.   th1=ioffsetof(struct chclass,pos1);ot1=ioffsetof(struct chclass,pos2);
  969.   maxdepth=(jt_type)~(jt_type)0;depth=1;thiss=other=code=(s=r)-1;bestval=0;
  970.   stack=0;goto nostack;
  971.   do          /* now flood the tree from the left, counting the distance */
  972.    { th1^=XOR1;ot1^=XOR1;thiss=other;other=code;stack=0;depth++;
  973.      do                     /* pop next entry off this pc-stack */
  974.       { thiss=PC(s=thiss,th1);PC(s,th1)=0;s=s->stack;goto nostack;
  975.     do
  976.        for(s=stack->spawn,stack=stack->stack;;)   /* empty epsilon stack */
  977. nostack:    { switch(s->opc-OPB)
  978.            { case OPC_EPS-OPB:s->stack=stack;s=(stack=s)->next;
  979.             continue;
  980. #ifndef RE_pNOSUB
  981.          case OPC_GOP-OPB:case OPC_GCL-OPB:s=s->stack;continue;
  982. #endif                               /* maxjump determined */
  983.          case OPC_FIN-OPB:maxdepth=depth;break;
  984.          case OPC_DOT-OPB:case OPC_CLASS-OPB:
  985.           { register unsigned c;
  986.             c=OPB-1;
  987.             do
  988.              { if(s->opc==OPC_CLASS)
  989.             { if(!bit_test(Cc(s,c),c))
  990.                  continue;
  991.             }
  992. #ifndef RE_nNEWLINE
  993. #ifdef RE_pNEWLINE
  994.                else if(c=='\n')
  995. #else
  996.                else if(c=='\n'&&gpreg->re_flags®_NEWLINE)
  997. #endif
  998.               continue;
  999. #endif
  1000.                jt[c]=depth;
  1001.              }
  1002.             while(c--);          /* loop through the whole alphabet */
  1003.             goto acc_st;
  1004.           }
  1005.          case OPC_BOL-OPB:case OPC_EOL-OPB:jt['\n']=depth;goto acc_st;
  1006.          default:jt[s->opc]=depth;    /* if state not yet pushed and */
  1007. acc_st:            if(!PC(s,ot1)&&!Cc(s,pos2.wh_))  /* still in the running */
  1008.              { PC(s,ot1)=other;other=s;
  1009.                if(depth==maxdepth)             /* last rounds? */
  1010.               Cc(s,pos2.wh_)=s;            /* knock him out */
  1011.              }
  1012.            }
  1013.           break;
  1014.         }
  1015.     while(stack);
  1016.       }
  1017.      while(thiss!=code);           /* still not done with this pass? */
  1018.      if(gpreg->re_flags®_ICASE)
  1019.       { unsigned i=OPB;
  1020.     do
  1021.        if(isupper(--i))           /* fill the uppercase values with the */
  1022.           jt[i]=jt[Tolower(i)];               /* lowercase ones */
  1023.     while(i);
  1024.       }
  1025.      if(depth==maxdepth)                /* already at the limit? */
  1026.     depth--;                 /* keep our depth within bounds */
  1027.      ;{ jt_type*jp;unsigned i;goodness better;
  1028.     jp=jt+(i=OPB);better=depth;
  1029.     do
  1030.        if(i--,*--jp>depth)                   /* out of bounds? */
  1031.           *jp=depth;
  1032.        else if(isprint(i))              /* statistically relevant? */
  1033.           better+=depth-*jp;         /* add its weight to the rating */
  1034.     while(i);
  1035.     if(better-bestval>0)         /* is this one better than our old one? */
  1036.      { jt_type*jpb;                 /* it's better, so copy it over */
  1037.        bestval=better;gpreg->re_maxjump=depth-1;i=OPB;jpb=bt;
  1038.        while(*jpb++=depth-*jp++,--i);
  1039.      }
  1040.       }
  1041.    }
  1042.   while(other!=code);                  /* done with every thread? */
  1043. #ifndef RE_STRLEN
  1044.   *bt=0;                 /* make sure that \0 always matches */
  1045. #endif
  1046. #else /* RE_nJUMP_TABLE */
  1047. { bit_type*jt=Jtable(gpreg->re_finpoint);
  1048.   ;{ register struct eps*stack,*s;
  1049.      initbitm(jt,1);stack=0;s=r;goto nxt3;           /* preset our bitmask */
  1050.      do               /* now examine all the candidates that could be first */
  1051.     for(s=stack->spawn,stack=stack->stack;;)
  1052. nxt3:     { switch(s->opc-OPB)
  1053.         { case OPC_EPS-OPB:s->stack=stack;s=(stack=s)->next;continue;
  1054. #ifndef RE_pNOSUB
  1055.           case OPC_GOP-OPB:case OPC_GCL-OPB:s=s->stack;continue;
  1056. #endif                    /* pity, mark everything as eligible */
  1057.           case OPC_FIN-OPB:case OPC_DOT-OPB:initbitm(jt,0);goto bailout;
  1058.           case OPC_CLASS-OPB:
  1059.          ;{ size_t i;bit_type*from;
  1060.             i=maxindex(Cc(s,c))+1;from=Cc(s,c);
  1061.             while(*jt++|=*from++,--i);
  1062.           }
  1063.          jt-=maxindex(Cc(s,c))+1;break;
  1064.           case OPC_BOL-OPB:case OPC_EOL-OPB:bseti(VS jt,'\n',1);break;
  1065.           default:bseti(VS jt,s->opc,1);
  1066.         }
  1067.        break;
  1068.      }
  1069.      while(stack);
  1070.    }
  1071. bailout:
  1072. #ifndef RE_STRLEN
  1073.   bseti(VS jt,'\0',1);             /* make sure that \0 always matches */
  1074. #endif
  1075. #endif /* RE_nJUMP_TABLE */
  1076. }
  1077.  
  1078. #ifndef reg_malloc
  1079. #include <stdlib.h>            /* malloc() realloc() free() */
  1080.  
  1081. void
  1082.  *(*reg_malloc)P((size_t size))=malloc,
  1083.  *(*reg_realloc)P((void*ptr,size_t size))=realloc,
  1084.  (*reg_free)P((void*ptr))=free;
  1085. #endif
  1086.  
  1087. regcomp(preg,pattern,cflags)regex_t*const preg;const char*const pattern;
  1088. { struct eps*s;
  1089. #ifndef RE_nCONCUR_COMPILE
  1090.   struct Vs vss;                /* virtual static struct :-) */
  1091. #define vs    (&vss)
  1092. #endif
  1093. #ifndef RE_nCASE_TABLE
  1094.   if(!bothcase[OPB-1])             /* already initialised case tables? */
  1095.    { register unsigned c=OPB-1;        /* no, so go through the entire alphabet */
  1096.      while(igncase[bothcase[c]=c]=isupper(c)?tolower(c):c,c--);
  1097.    }
  1098. #endif
  1099. #ifdef RE_NSUBMAX
  1100.   if(((gpreg=preg)->re_flags=cflags)®_NSUBMAX)     /* max. re_nsub given? */
  1101.      mnmatch=preg->re_nsub;
  1102. #else
  1103.   (gpreg=preg)->re_flags=cflags;     /* store the flags, for later reference */
  1104. #endif
  1105.   preg->re_nsub=errorno=(char*)progid-(char*)progid;preg->re_es.re_stack=0;
  1106.   p=(uchar*)pattern;r=Ceps&aleps;cachea=0;por(VS Ceps 0); /* 1st a trial run */
  1107.  /*
  1108.   *    Possible ANSI violation here.  The assumption is that:
  1109.   *        (&aleps+a)+b==&aleps+c for any positive integers a,b,c
  1110.   *                        where a+b==c
  1111.   */
  1112.   ;{ size_t i;
  1113.      if(!(r=preg->re_compiled=s=reg_malloc((i=dif(r,&aleps))+     /* allocate */
  1114.       mx(ioffsetof(struct eps,stack)+SZ(eps*),SZ(aligar)))))   /* the memory */
  1115.     return REG_ESPACE;
  1116.      p=(uchar*)pattern;preg->re_nsub=0;      /* back to the start of the source */
  1117.      if(!por(VS epso(s,i)))              /* now compile it for real */
  1118.     error(VS REG_EPAREN);
  1119.    }
  1120.   (Ceps(preg->re_finpoint=r))->opc=OPC_FIN;              /* add end */
  1121. #ifndef RE_SURE_MINIMAL
  1122.   r->stack=0;
  1123.   for(r=s;;s=skiplen(s))         /* simplify the compiled code (i.e. */
  1124.    { switch(s->opc)              /* take out cyclic epsilon references) */
  1125.       { case OPC_EPS:p=(uchar*)s;fillout(VS &s);           /* check tree */
  1126.     default:continue;
  1127.     case OPC_FIN:;                         /* finished */
  1128.       }
  1129.      break;
  1130.    }
  1131. #endif
  1132.   cflags|=REG_SIMPLE;
  1133. #ifndef RE_DUMB_ANCHOR
  1134.   ;{ register struct eps*stack;
  1135.      stack=0;s=r;goto nxt;
  1136.      do
  1137.     for(s=stack->spawn,stack=stack->stack;;)
  1138. nxt:     { switch(s->opc)
  1139.         { case OPC_EPS:s->stack=stack;s=(stack=s)->next;continue;
  1140. #ifndef RE_pNOSUB
  1141.           case OPC_GOP:case OPC_GCL:s=s->stack;continue;
  1142. #endif
  1143.           case OPC_BOL:Cc(s,pos1.wh_)=0;         /* found a real OPC_BOL */
  1144.         }    /* anything else is irrelevant (prune the search to the top) */
  1145.        break;
  1146.      }
  1147.      while(stack);
  1148.    }
  1149.   for(s=r;;s=skiplen(s))               /* search through it linearly */
  1150.    { switch(s->opc)
  1151.       { case OPC_EOL:
  1152.      { register struct eps*t,*stack;
  1153.        stack=0;t=s->stack;goto nxt1;
  1154.        do
  1155.           for(t=stack->spawn,stack=stack->stack;;)
  1156. nxt1:           { switch(t->opc)
  1157.           { case OPC_EPS:t->stack=stack;t=(stack=t)->next;continue;
  1158. #ifndef RE_pNOSUB
  1159.             case OPC_GOP:case OPC_GCL:t=t->stack;continue;
  1160. #endif
  1161.             case OPC_FIN:goto eol_ok;          /* ok, reached the end */
  1162.           }                  /* not the end, look elsewhere */
  1163.          break;
  1164.            }
  1165.        while(stack);
  1166.        s->opc=C_EOL;        /* so it turned out to be a fake OPC_EOL */
  1167. err_anch:
  1168. #ifndef RE_nERROR_DETECT
  1169.        p=(void*)Cc(s,pos1.wh_);        /* adjust the source pointer */
  1170. #ifndef RE_pEXTENDED
  1171.        if(cflags®_EXTENDED)
  1172. #endif
  1173. #endif
  1174.           error(VS REG_BADRPT);    /* so that the error is at the right */
  1175.        continue;                           /* offset */
  1176.      }
  1177.     case OPC_BOL:
  1178.        if(Cc(s,pos1.wh_))                    /* fake OPC_BOL? */
  1179.         { s->opc=C_BOL;goto err_anch;          /* yep, convert it */
  1180.         }
  1181. #ifndef RE_pNOSUB
  1182.     case OPC_GOP:case OPC_GCL:
  1183. #endif
  1184. eol_ok:       cflags&=~REG_SIMPLE;
  1185.     default:continue;
  1186.     case OPC_FIN:;                  /* end of the line, *stop* */
  1187.       }
  1188.      break;
  1189.    }
  1190. #else /* RE_DUMB_ANCHOR */
  1191.   for(s=r;;s=skiplen(s))               /* search through it linearly */
  1192.    { switch(s->opc)
  1193.       { case OPC_FIN:break;
  1194.     case OPC_EOL:case OPC_BOL:case OPC_GOP:case OPC_GCL:
  1195.        cflags&=~REG_SIMPLE;continue;
  1196.       }
  1197.      break;
  1198.    }
  1199. #endif /* RE_DUMB_ANCHOR */
  1200.   if(errorno)                     /* did we detect any error? */
  1201.    { preg->re_erroffset=(const char*)preg->re_es.re_stack-pattern;
  1202.      preg->re_flags=cflags|REG_ERROR;
  1203.    }
  1204. #ifndef RE_EXEC_ERROR
  1205.   else
  1206. #endif
  1207.      initjtable(VSO);
  1208.   return errorno;                   /* phew, compilation finished */
  1209. }
  1210.  
  1211. #ifdef RE_nCASE_TABLE
  1212. #define CHECKCASE(i)    (ign_case&&TO_LOWER(i))
  1213. #else
  1214. #define CHECKCASE(i)    ((i)=transcase[i])
  1215. #endif
  1216.  
  1217. static struct eps*cleantail(start,code,thiss,th1)const uchar*const start;
  1218.  const struct eps*const code;struct eps*thiss;const unsigned th1;
  1219. { register struct eps**t;
  1220.   while(thiss!=code)              /* not at the end of this pc-stack */
  1221.      if(PCps(t,thiss,th1)>start)              /* did it start later? */
  1222.     thiss= *t,*t=0;                     /* yep, so throw it out */
  1223.      else                        /* no, proceed carefully */
  1224.       { register struct eps**s;
  1225.     while(*t!=code)              /* not at the end of this pc-stack */
  1226.        if(PCps(s,*t,th1)>start)              /* did it start later? */
  1227.           *t= *s,*s=0;                 /* yep, so throw it out */
  1228.        else
  1229.           t=s;                          /* no, proceed */
  1230.     break;
  1231.       }
  1232.   return thiss;
  1233. }
  1234.  
  1235. #ifdef RE_STRLEN
  1236. regexec(preg,string,length,nmatch,pmatch,eflags)/*const*/regex_t*preg;
  1237.  const char*const string;size_t length;size_t nmatch;regmatch_t pmatch[];
  1238. #else
  1239. regexec(preg,string,nmatch,pmatch,eflags)/*const*/regex_t*preg;
  1240.  const char*const string;size_t nmatch;regmatch_t pmatch[];
  1241. #endif /* RE_STRLEN */
  1242. { register struct eps*code;const uchar*founds,*founde=0;
  1243. #ifdef RE_nCASE_TABLE
  1244.   unsigned ign_case;
  1245. #else
  1246.   const uchar*transcase;
  1247. #endif
  1248. #ifdef RE_STRLEN
  1249.   size_t len;
  1250. #endif
  1251.   ;{ register struct eps*other,*thiss;unsigned th1,ot1;const uchar*str;
  1252.      struct eps*initstack,*initcode;struct mchar virteol;
  1253.      virteol.next1_=preg->re_finpoint;virteol.p1_.st_=virteol.p2_.st_=0;
  1254. #ifdef RE_nCASE_TABLE
  1255.      ign_case=(eflags|=preg->re_flags)®_ICASE;
  1256. #else
  1257.      transcase=(eflags|=preg->re_flags)®_ICASE?igncase:bothcase;
  1258. #endif
  1259.      if((code=preg->re_compiled)->opc==OPC_EPS)
  1260.     initcode=(initstack=code)->next;         /* epsilon at the start */
  1261.      else
  1262.     initcode=code,initstack=0;             /* regular at the start */
  1263.      th1=ioffsetof(struct chclass,pos1);ot1=ioffsetof(struct chclass,pos2);
  1264.     /*
  1265.      *    Possible ANSI violation here.  The assumption is that:
  1266.      *        (struct eps*)malloc(sizeof(struct eps))-1!=0
  1267.      */
  1268.      thiss=other= --code;str=(uchar*)string-1;       /* init pc-stack pointers */
  1269. #ifdef RE_STRLEN
  1270.      founds=(uchar*)string+2+(len=length);     /* saves us a compare later */
  1271. #else
  1272.      founds=0;                   /* there is no other way in this case */
  1273. #endif
  1274.      ;{ register struct eps*s,*stack;          /* proper pre-conditioning */
  1275.     stack=initstack;s=initcode;goto nxt;
  1276.     do                  /* make sure \n does not match BOL */
  1277.        for(s=stack->spawn,stack=stack->stack;;)
  1278. nxt:        { switch(s->opc)
  1279.            { case OPC_EPS:s->stack=stack;s=(stack=s)->next;continue;
  1280. #ifndef RE_pNOSUB
  1281.          case OPC_GOP:case OPC_GCL:s=s->stack;continue;
  1282. #endif
  1283.          case OPC_FIN:                     /* special case */
  1284. #ifndef RE_COMMON_SUBXP
  1285.           { register char*c;
  1286.             if(!Pci(&virteol,ot1))         /* state not yet pushed */
  1287.                Pc()=other,other=Ceps&virteol,Pcp()=string;
  1288.           }
  1289. #else /* RE_COMMON_SUBXP */
  1290.             if(!PC(&virteol,ot1))         /* state not yet pushed */
  1291.              { PC(&virteol,ot1)=other;
  1292.                PCp(other=Ceps&virteol,ot1)=string;
  1293.              }
  1294. #endif /* RE_COMMON_SUBXP */
  1295.             break;
  1296.          case OPC_BOL:
  1297.             if(!(eflags®_NOTBOL))
  1298. #ifndef RE_COMMON_SUBXP
  1299.              { register char*c;
  1300.                if(!Pci(s,ot1))             /* state not yet pushed */
  1301.               Pc()=other,other=s,Pcp()=str;
  1302.              }
  1303. #else /* RE_COMMON_SUBXP */
  1304.                if(!PC(s,ot1))             /* state not yet pushed */
  1305.               PC(s,ot1)=other,PCp(other=s,ot1)=str;
  1306. #endif /* RE_COMMON_SUBXP */
  1307.            }
  1308.           break;
  1309.         }
  1310.     while(stack);
  1311.       }
  1312. #ifdef RE_STRLEN
  1313.      if(len)
  1314. #endif
  1315.       { register struct eps*s,*stack;const uchar*start;unsigned i;
  1316. #ifdef RE_nJUMP_TABLE
  1317.     bit_type*jt;
  1318. #else
  1319.     jt_type*jt;unsigned maxjump=preg->re_maxjump;
  1320. #endif
  1321.     jt=Jtable(preg->re_finpoint);
  1322. #ifndef RE_STRLEN
  1323.     while(i= *++str)
  1324.      {
  1325. #else
  1326.     do
  1327.      { i= *++str;             /* get the next real-text character */
  1328. #endif                         /* switch this & other pc-stack */
  1329.        CHECKCASE(i);th1^=XOR1;ot1^=XOR1;thiss=other;other=code;
  1330.        stack=initstack;
  1331.        if(s=initcode)
  1332.         { if(thiss==code)                  /* automaton idle? */
  1333. #ifndef RE_nJUMP_TABLE
  1334.          if(maxjump)                  /* can we jump at all? */
  1335.           { register unsigned jump=maxjump;
  1336.             register const uchar*jstr=str;
  1337. shortcut:        do
  1338. #ifdef RE_STRLEN
  1339.              { if(jump>=len)          /* want to jump over the edge? */
  1340.             { if(jump!=len||jt['\n'])        /* virtual edge? */
  1341.                  goto ret;             /* no, the real one */
  1342.               jstr+=jump;jump=0;break;     /* might be virtual */
  1343.             }
  1344.                len-=jump;                /* make the jump */
  1345. #ifdef RE_ABORT_EXPR
  1346.                if(RE_ABORT_EXPR)
  1347.               goto ret;
  1348. #endif
  1349.              }
  1350.             while(jump=(jt[*(jstr+=jump)]));   /* determine new jump */
  1351. #else /* RE_STRLEN */
  1352. #ifdef RE_MEMCHR
  1353.              {
  1354.                switch(jump)
  1355.             { case 2:
  1356.                  if(!jstr[1])
  1357.                 goto ret;
  1358.                  break;
  1359.               default:
  1360.                  if(memchr(jstr+1,'\0',(size_t)jump-1))
  1361.                 goto ret;
  1362.               case 1:;
  1363.             }
  1364. #else
  1365.              { while(--jump)             /* jump in little steps */
  1366.               if(!*++jstr)         /* so as not to overlook the \0 */
  1367.                  goto ret;
  1368. #endif /* RE_nMEMCHR */
  1369. #ifdef RE_ABORT_EXPR
  1370.                if(RE_ABORT_EXPR)
  1371.               goto ret;
  1372. #endif
  1373.              }
  1374. #ifdef RE_MEMCHR
  1375.             while(jump=jt[*(jstr+=jump)]);
  1376. #else
  1377.             while(jump=jt[*++jstr]);
  1378. #endif
  1379.             if(!*jstr&&jt['\n'])             /* virtual \0 ? */
  1380.                goto ret;
  1381. #endif /* RE_STRLEN */
  1382.             do                     /* go back on our steps */
  1383.                if(jt[*--jstr]>++jump)        /* impossible match? */
  1384.             { jump=jt[*jstr];goto shortcut;         /* jump forward */
  1385.             }
  1386.             while(jump!=maxjump);       /* not at target position */
  1387.             i= *(str=jstr);                 /* load and run */
  1388.           }
  1389.          else
  1390. #define JT_TEST(jt,i)    (jt[i])           /* !maxjump, so misuse jt as a bitmap */
  1391. #else /* RE_nJUMP_TABLE */
  1392. #define JT_TEST(jt,i)    (!bit_test(jt,i))
  1393. #endif /* RE_nJUMP_TABLE */
  1394.             if(JT_TEST(jt,i))
  1395.              { register const uchar*jstr=str;
  1396.                do
  1397.             {
  1398. #ifdef RE_STRLEN
  1399.               if(!--len)
  1400.                { len++;break;        /* give `$' a chance */
  1401.                }
  1402. #endif
  1403. #ifdef RE_ABORT_EXPR
  1404.               if(RE_ABORT_EXPR)
  1405.                  goto ret;
  1406. #endif
  1407.             }
  1408.                while(jstr++,JT_TEST(jt,*jstr));
  1409. #ifndef RE_STRLEN
  1410.                if(!(i= *(str=jstr)))
  1411.               i=*--str;            /* give `$' a chance */
  1412. #else
  1413.                i= *(str=jstr);                 /* load and run */
  1414. #endif
  1415.              }
  1416.           start=str;goto nostack;
  1417.         }
  1418.        else if(thiss==code)
  1419.           goto foundit;
  1420.        do                 /* pop next entry off this pc-stack */
  1421. #ifndef RE_COMMON_SUBXP
  1422.         { s=thiss->stack;
  1423.           ;{ register char*c;
  1424.          thiss=Pci(thiss,th1);Pc()=0;start=Pcp();
  1425.            }
  1426. #else /* RE_COMMON_SUBXP */
  1427.         { thiss=PC(s=thiss,th1);PC(s,th1)=0;start=PCp(s,th1);s=s->stack;
  1428. #endif /* RE_COMMON_SUBXP */
  1429.           goto nostack;
  1430.           do             /* pop next entry off the epsilon-stack */
  1431.          for(s=stack->spawn,stack=stack->stack;;)
  1432. nostack:      { switch(s->opc-OPB)
  1433.              { default:
  1434.               if(i==s->opc)          /* regular character match */
  1435.                  goto yep;
  1436.               break;
  1437.                case OPC_BOL-OPB:
  1438.               if(i=='\n')          /* reset the start pointer */
  1439. #ifndef RE_COMMON_SUBXP
  1440.                { register char*c;
  1441.                  if(!Pci(s,ot1))         /* state not yet pushed */
  1442.                 Pc()=other,other=s;
  1443.                  Pcp()=str;
  1444. #else /* RE_COMMON_SUBXP */
  1445.                { if(!PC(s,ot1))         /* state not yet pushed */
  1446.                 PC(s,ot1)=other,other=s;
  1447.                  PCp(s,ot1)=str;
  1448. #endif /* RE_COMMON_SUBXP */
  1449.                }
  1450.               break;
  1451.                case OPC_EOL-OPB:
  1452.               if(i=='\n')         /* only allow OPC_FIN to follow */
  1453.                { s=Ceps&virteol;goto yep;         /* this one */
  1454.                }
  1455.               break;    /* push spawned branch on the work-stack */
  1456.                case OPC_EPS-OPB:s->stack=stack;s=(stack=s)->next;
  1457.               continue;
  1458. #ifndef RE_pNOSUB
  1459.                case OPC_GOP-OPB:case OPC_GCL-OPB:s=s->stack;continue;
  1460. #endif
  1461.                case OPC_FIN-OPB:      /* hurray!  complete match */
  1462. #ifdef RE_STRLEN
  1463.               if(start<=founds)       /* will always match once */
  1464. #else
  1465.               if(start<=founds||!founds)        /* extra compare */
  1466. #endif
  1467.                { founde=str;           /* one past the start */
  1468.                  if(!nmatch)
  1469.                 goto ret;          /* only report success */
  1470.                  thiss=cleantail(founds=start,code,thiss,th1);
  1471.                  other=cleantail(start,code,other,ot1);
  1472.                  initcode=initstack=0;   /* don't start anything */
  1473.                }                          /* new */
  1474.               break;
  1475.                case OPC_CLASS-OPB:
  1476.               if(bit_test(Cc(s,c),i))
  1477.                  goto yep;               /* character in class */
  1478.               break;
  1479.                case OPC_DOT-OPB:             /* dot-wildcard */
  1480. #ifndef RE_nNEWLINE
  1481. #ifdef RE_pNEWLINE
  1482.               if(i!='\n')
  1483. #else
  1484.               if(i!='\n'||!(eflags®_NEWLINE))
  1485. #endif
  1486. #endif
  1487. #ifndef RE_COMMON_SUBXP
  1488.                { register char*c;
  1489. yep:                 if(!Pci(s,ot1))         /* state not yet pushed */
  1490.                   { Pc()=other;other=s;Pcp();
  1491. earlier:            PcP()=start;
  1492.                   }
  1493.                  else if((uchar*)Pcp()>start)
  1494.                 goto earlier;
  1495.                }
  1496. #else /* RE_COMMON_SUBXP */
  1497. yep:                 if(!PC(s,ot1))         /* state not yet pushed */
  1498.                   { PC(s,ot1)=other;other=s;
  1499. earlier:            PCp(s,ot1)=start;
  1500.                   }            /* is it not the earliest match? */
  1501.                  else if((uchar*)PCp(s,ot1)>start)
  1502.                 goto earlier;
  1503. #endif /* RE_COMMON_SUBXP */
  1504.              }            /* push location onto other pc-stack */
  1505.             break;
  1506.           }
  1507.           while(stack);              /* the work-stack is not empty */
  1508.         }
  1509.        while(thiss!=code);               /* this pc-stack is not empty */
  1510. #ifdef RE_ABORT_EXPR
  1511.        if(RE_ABORT_EXPR)
  1512.           goto ret;
  1513. #endif
  1514.      }
  1515. #ifdef RE_STRLEN
  1516.     while(--len);                     /* still text to search */
  1517.       }
  1518.      str++;                         /* one past the end */
  1519. #else
  1520.       }                                  /* out of text */
  1521. #endif                         /* proper post-conditioning */
  1522.      ;{ register struct eps*t,*s,*stack;unsigned i,no_eol;
  1523.     for(t=other,no_eol=eflags®_NOTEOL;t!=code;t=PC(t,ot1))
  1524.      { s=t->stack;i=0;stack=0;goto nxt2;
  1525.        do
  1526.           for(s=stack->spawn,stack=stack->stack;;)
  1527. nxt2:           { switch(s->opc)
  1528.           { case OPC_EPS:s->stack=stack;s=(stack=s)->next;continue;
  1529.             case OPC_EOL:
  1530.                if(no_eol)           /* can we match this EOL? */
  1531.               break;
  1532.                i=1;            /* skip one further in that case */
  1533. #ifndef RE_pNOSUB
  1534.             case OPC_GOP:case OPC_GCL:
  1535. #endif
  1536.                s=s->stack;continue;
  1537.             case OPC_FIN:
  1538.              { const uchar*start;
  1539. #ifdef RE_STRLEN
  1540.                if((start=PCp(t,ot1))<=founds)
  1541. #else
  1542.                if((start=PCp(t,ot1))<=founds||!founds)
  1543. #endif                          /* assign match + offset i */
  1544.               founds=start,founde=str+i;
  1545.              /*
  1546.               *    Possible ANSI violation here.
  1547.               *    The assumption is that `founde' can be
  1548.               *    assigned a value that is two elements
  1549.               *    past the last element of `string'.
  1550.               */
  1551.              }
  1552.           }
  1553.          break;
  1554.            }
  1555.        while(stack);
  1556.      }
  1557.       }
  1558. ret:;
  1559. #ifndef RE_nREUSABLE
  1560.      do
  1561.       { register struct eps*t;
  1562.     while(thiss!=code)                /* cleanup this pc-stack */
  1563.        thiss=PC(t=thiss,th1),PC(t,th1)=0;
  1564.     thiss=other;                    /* and the other one */
  1565.       }
  1566.      while((th1^=XOR1)==ot1);
  1567. #endif
  1568.    }
  1569. #ifdef RE_ABORT_EXPR
  1570.   if(RE_ABORT_EXPR)
  1571.      return REG_ABORT;
  1572. #endif
  1573. foundit:
  1574.   if(!nmatch||!founde&&eflags®_NOSUB)
  1575.      goto retmatch;
  1576.   ;{ unsigned lsub=nmatch;
  1577.      while(--lsub)                 /* clear pmatch array first */
  1578.     pmatch[lsub].rm_ep=0;
  1579.    }
  1580. #define for_CLEAN_PMATCH(nmatch,lsub)    \
  1581.   for(;;)\
  1582.      if(nmatch<=lsub||!pmatch[lsub].rm_ep)\
  1583.     lsub--;\
  1584.      else if(lsub&&pmatch[lsub].rm_sp>=(char*)str)\
  1585.     pmatch[lsub--].rm_ep=0;\
  1586.      else
  1587. #define PMATCH_so(str)    \
  1588.   if(nmatch>(lsub=Go(s,gopp.nr)))\
  1589.      pmatch[lsub].rm_sp=(char*)str
  1590. #define PMATCH_eo(str)    \
  1591.   if(nmatch>Gc(s,gopp.nr))\
  1592.      pmatch[Gc(s,gopp.nr)].rm_ep=(char*)str
  1593.                  /* any match at all?  spare us the details? */
  1594.   if((pmatch->rm_ep=(char*)founde)&&
  1595.    (pmatch->rm_sp=(char*)founds,!(eflags®_SIMPLE)))
  1596.    { unsigned sol,eol;             /* second automaton, for filling pmatch */
  1597.      ;{ struct evoi*cstp,*stp,*estp;register struct eps*s;const uchar*str,*end;
  1598.     unsigned i,no_eol;
  1599. #ifndef RE_pNOSUB
  1600.     unsigned lsub=0;
  1601. #endif
  1602. #ifdef RE_EXEC_ERROR
  1603.     if(eflags®_ERROR)
  1604.      { preg->re_flags=eflags&~REG_ERROR;goto newstack;
  1605.      }
  1606. #endif
  1607.     if(stp=preg->re_es.re_stack)
  1608.        estp=(struct evoi*)stp->wh_;
  1609.     else
  1610. newstack:  estp=STARTSTACK+(stp=reg_malloc(STARTSTACK*SZ(evoi)));
  1611.     cstp=stp;s=code+1;end=founde--;
  1612. #ifdef RE_STRLEN
  1613.     if((char*)end>string+length)
  1614.        end--;            /* limit end to the non-virtual area */
  1615.     no_eol=(char*)end<string+length&&*end!='\n';
  1616. #else
  1617.     if((char*)end>string&&!end[-1])
  1618.        end--;            /* limit end to the non-virtual area */
  1619.     no_eol= *end!='\n'&&*end;
  1620. #endif                     /* upcoming preincrement, so backup */
  1621.     str=founds-1;eol=0;
  1622.     if((char*)founds<string)    /* match before the start of string? */
  1623.      { str++;goto virtual_newline;
  1624.      }
  1625.     for(sol=0;;s=s->stack)            /* update the pc to the next */
  1626.      { if(++str<end)                /* inside our match? */
  1627. goon:        { i= *str;                   /* read character from stream */
  1628. redo:          switch(s->opc-OPB)         /* switch to the current opcode */
  1629.            { default:case OPC_FIN-OPB:
  1630.             CHECKCASE(i);
  1631.             if(i==s->opc)          /* compare a regular character */
  1632.                continue;       /* a match, simply go to the next */
  1633.             break;
  1634.          case OPC_DOT-OPB:
  1635. #ifndef RE_nNEWLINE
  1636. #ifdef RE_pNEWLINE
  1637.             if(i!='\n')
  1638. #else
  1639.             if(i!='\n'||!(eflags®_NEWLINE))
  1640. #endif
  1641. #endif
  1642.                continue;
  1643.             break;
  1644.          case OPC_CLASS-OPB:
  1645.             if(bit_test(Cc(s,c),i))
  1646.                continue;
  1647.             break;
  1648.          case OPC_EPS-OPB:              /* push(str,s->spawn); */
  1649.             if(estp==cstp)
  1650.              { size_t t;
  1651.                if(!(cstp=reg_realloc(stp,
  1652.             t=dif(cstp,stp)+INCSTACK*SZ(evoi))))
  1653.             { eflags|=REG_LOWMEM|REG_OUTOFMEM;goto complete_match;
  1654.             }
  1655.                stp=cstp;cstp=(estp=(struct evoi*)geno(stp,t))-INCSTACK;
  1656.              }      /* save the junction on the stack, pick one branch */
  1657.             cstp->wh_=str;cstp++->st_=s->spawn;s=s->next;goto redo;
  1658. #ifndef RE_pNOSUB
  1659.          case OPC_GOP-OPB:PMATCH_so(str);s=s->stack;goto redo;
  1660.          case OPC_GCL-OPB:PMATCH_eo(str);s=s->stack;goto redo;
  1661. #endif
  1662.          case OPC_EOL-OPB:
  1663.             if(i=='\n'&&str==founde)
  1664.              { eol=1;continue;
  1665.              }
  1666.             break;
  1667.          case OPC_BOL-OPB:
  1668.             if(i=='\n'&&str==founds)
  1669.              { sol=1;continue;
  1670.              }
  1671.            }
  1672.         }
  1673.        else
  1674.         { register struct eps*stack=0;
  1675.           goto nxt3;           /* proper post-conditioning again */
  1676.           do
  1677.          for(s=stack->spawn,stack=stack->stack;;s=s->stack)
  1678. nxt3:          { switch(s->opc)
  1679.              { case OPC_EPS:s->stack=stack;s=(stack=s)->next;
  1680.               goto nxt3;
  1681.                case OPC_EOL:
  1682.               if(no_eol)
  1683.                  break;
  1684.               continue;
  1685. #ifndef RE_pNOSUB
  1686.                case OPC_GOP:PMATCH_so(str);continue;
  1687.                case OPC_GCL:PMATCH_eo(str);continue;
  1688. #endif
  1689.                case OPC_FIN:goto complete_match;       /* yahoe! */
  1690.              }
  1691. #ifndef RE_pNOSUB
  1692.             for_CLEAN_PMATCH(nmatch,lsub)
  1693.                break;
  1694. #endif
  1695.             break;
  1696.           }
  1697.           while(stack);
  1698.         }
  1699.        str=(--cstp)->wh_;s=cstp->st_;              /* pop(str,s); */
  1700. #ifndef RE_pNOSUB
  1701.        for_CLEAN_PMATCH(nmatch,lsub)
  1702. #endif
  1703.           if((char*)str<string)
  1704. virtual_newline:
  1705.            { i='\n';goto redo;
  1706.            }
  1707.           else
  1708.            { if(str<founde)
  1709.             eol=0;
  1710.          if(str==founds)
  1711.             sol=0;
  1712.          goto goon;
  1713.            }
  1714.      }
  1715. complete_match:           /* free the runtime stack or prepare it for later */
  1716.     preg->re_es.re_stack=eflags®_LOWMEM?
  1717.      (reg_free(stp),(struct evoi*)0):(stp->wh_=estp,stp);
  1718.     pmatch->rm_ep=(char*)str;        /* mark the end of the match */
  1719.       }
  1720.      if(sol)               /* adjust the starting point?  (due to a `^') */
  1721.       { unsigned lsub=nmatch;
  1722.     do
  1723.        if(pmatch[--lsub].rm_sp==(char*)founds)
  1724.           pmatch[lsub].rm_sp=(char*)founds+1;       /* shift it right */
  1725.     while(lsub);
  1726.       }
  1727.      if(eol)             /* adjust the ending point?  (due to a `$') */
  1728.       { unsigned lsub=nmatch;
  1729.     do
  1730.        if(pmatch[--lsub].rm_ep>(char*)founde)
  1731.           pmatch[lsub].rm_ep=(char*)founde;            /* shift it left */
  1732.     while(lsub);
  1733.       }
  1734.    }
  1735.   ;{ unsigned lsub=nmatch;
  1736.      do
  1737.     if(!pmatch[--lsub].rm_ep)          /* no match on this group? */
  1738. #ifdef RE_SUBSTR_PTR
  1739.        pmatch[lsub].rm_sp=0;      /* then wipe out the start as well */
  1740. #else
  1741.        pmatch[lsub].rm_so=pmatch[lsub].rm_eo= -1;  /* same, with offsets */
  1742.     else
  1743.      { pmatch[lsub].rm_so=(const char*)pmatch[lsub].rm_sp-string;
  1744.        pmatch[lsub].rm_eo=(const char*)pmatch[lsub].rm_ep-string;
  1745.      }
  1746. #endif
  1747.      while(lsub);
  1748.    }
  1749. retmatch:
  1750.   return eflags®_OUTOFMEM?REG_ESPACE:founde?0:REG_NOMATCH;
  1751. }
  1752.  
  1753. #ifdef RE_COPY
  1754. #define cp_s(memb)    (dest->memb=src->memb)
  1755. #define cp_e(memb)    (d->memb=epso(d,dif(s->memb,s)))
  1756.  
  1757. static void copyclass(to,from)bit_type*to;const bit_type*from;
  1758. { register unsigned i=bit_mindex(OPB);
  1759.   while(*to++= *from++,--i);
  1760. }
  1761.  
  1762. regcopy(dest,src)regex_t*const dest;const regex_t*const src;
  1763. { register struct eps*s,*d;
  1764.   cp_s(re_nsub);cp_s(re_flags);                 /* clone the easy parts */
  1765. #ifndef RE_nJUMP_TABLE
  1766.   cp_s(re_maxjump);
  1767. #endif
  1768.   dest->re_compiled=0;
  1769.   if(src->re_flags®_ERROR)
  1770.      cp_s(re_erroffset);
  1771.   else
  1772.      dest->re_es.re_stack=0;
  1773.   if(!(s=src->re_compiled))           /* hmmm..., missing source regexp */
  1774.      return REG_BADPAT;                      /* allocate some space */
  1775.   if(!(d=dest->re_compiled=reg_malloc(dif(src->re_finpoint,s)+
  1776.    mx(ioffsetof(struct eps,stack)+SZ(eps*),SZ(aligar)))))
  1777.      return REG_ESPACE;                             /* oops */
  1778.   for(;;d=skiplen(d),s=skiplen(s))            /* step through them */
  1779.    { switch((d->opc=s->opc)-OPB)              /* copying opcodes */
  1780.       { case OPC_EPS-OPB:cp_e(spawn);cp_e(next);continue;
  1781.     case OPC_FIN-OPB:
  1782. #ifdef RE_nJUMP_TABLE
  1783.        copyclass(Jtable(dest->re_finpoint=d),Jtable(s));
  1784. #else
  1785.        ;{ register jt_type*to;register const jt_type*from;
  1786.           register unsigned i;
  1787.           i=OPB;to=Jtable(dest->re_finpoint=d);from=Jtable(s);
  1788.           while(*to++= *from++,--i);
  1789.         }
  1790. #endif
  1791.        return 0;
  1792. #ifndef RE_nNOSUB
  1793.     case OPC_GOP-OPB:
  1794. #ifndef gcl
  1795.        Go(d,gopp.nr)=Go(s,gopp.nr);break;
  1796. #endif
  1797.     case OPC_GCL-OPB:
  1798.        Gc(d,gopp.nr)=Gc(s,gopp.nr);break;
  1799. #endif /* RE_nNOSUB */
  1800.     case OPC_CLASS-OPB:copyclass(Cc(d,c),Cc(s,c));
  1801.     default:case OPC_DOT-OPB:case OPC_BOL-OPB:case OPC_EOL-OPB:
  1802.        initsimp(d,d);
  1803.       }
  1804.      cp_e(stack);                     /* simple next pointers */
  1805.    }
  1806. }
  1807. #endif /* RE_COPY */
  1808.  
  1809. void regfree(rg)regex_t*rg;
  1810. { if(rg->re_compiled)
  1811.    { reg_free(rg->re_compiled);rg->re_compiled=0;
  1812.      if(!(rg->re_flags®_ERROR)&&rg->re_es.re_stack)
  1813.     reg_free(rg->re_es.re_stack),rg->re_es.re_stack=0;
  1814.    }
  1815. }
  1816.  
  1817. #ifndef RE_nERROR_REPORT
  1818. static size_t catlim(dest,src,lim)register char*dest;register const char*src;
  1819.  register size_t lim;
  1820. { size_t len=strlen(src);
  1821.   while(lim&&*dest)                   /* search for the end of dest */
  1822.      dest++,lim--;
  1823.   if(lim)                       /* still space left in buffer */
  1824.    { while(--lim&&(*dest++= *src++));                   /* append src */
  1825.      *dest='\0';              /* make sure it is properly terminated */
  1826.    }
  1827.   return len;                    /* merely a counting service */
  1828. }
  1829.  
  1830. size_t regerror(errcode,preg,errbuf,errbuf_size)const regex_t*const preg;
  1831.  char*const errbuf;size_t errbuf_size;
  1832. { size_t needed,i;
  1833.   static const char*const error_msg[]=
  1834.    {"Failed to match","Invalid regular expression",
  1835.     "Invalid collating element","Invalid character class type","Trailing \\",
  1836.     "Number in \\digit invalid","[ ] imbalance","( ) imbalance",
  1837.     "{ } imbalance","Content of { } invalid",
  1838.     "Invalid endpoint in range expression","Out of memory",
  1839.     "Inappropriate use of magic character",
  1840. #ifdef RE_ABORT_EXPR
  1841.     "Search aborted"
  1842. #endif
  1843.     },atoffset[]=" at offset: ";
  1844.   if(errbuf_size)                       /* any target at all? */
  1845.      *errbuf='\0';                     /* clear out the target */
  1846.   needed=1;                   /* for the omnipresent terminating \0 */
  1847.   if(--errcode>=0&&errcode<=maxindex(error_msg))
  1848.    { needed+=catlim(errbuf,error_msg[errcode],errbuf_size);   /* regular msg */
  1849.      if(errcode&&preg&&(preg->re_flags&(REG_NOOFFSET|REG_ERROR))==REG_ERROR)
  1850.       { needed+=catlim(errbuf,atoffset,errbuf_size);        /* at offset */
  1851.     for(errcode=0,i=preg->re_erroffset;errcode++,i/=10;);
  1852.     needed+=errcode;errcode=1;i=preg->re_erroffset;
  1853.     do                           /* fill in the digits */
  1854.        if(needed-++errcode<errbuf_size)
  1855.           errbuf[needed-errcode]=hex2num[i%10];   /* coding it like this */
  1856.     while(i/=10);                  /* avoids linking in sprintf() */
  1857.     errbuf[(needed<=errbuf_size?needed:errbuf_size)-1]='\0';
  1858.       }
  1859.    }
  1860.   return needed;
  1861. }
  1862. #endif /* RE_nERROR_REPORT */
  1863.  
  1864. /*
  1865.  *    It might be hard to believe, but I generally dislike conditionally
  1866.  *    compiled code (especially when it is done to get the code working
  1867.  *    on vastly distinct architectures).
  1868.  *
  1869.  *    However, you might have noticed (I guess you could hardly have missed
  1870.  *    it :-) that I made an exception in this library.  I did it because:
  1871.  *    1. The conditional compilation constructs in this library have
  1872.  *       nothing to do with portability issues.
  1873.  *    2. This seemed to be the only way to have a relatively compact
  1874.  *       library, yet easily customisable to your personal taste.
  1875.  *
  1876.  *    But, I hope I never have to program/debug code like this in the
  1877.  *    future.     It comes close to a programmer's worst nightmare :-).
  1878.  */
  1879.